package puzzle.projecteuler.p200;

public class Problem191C {

	/**
	 * 先考虑由A和O组成，不含“AAA”，且长度为n的字符串数目f(n)。
	 * f(0)=1,f(1)=2,f(2)=4,f(3)=7
	 * f(n) = f(n-1) + f(n-2) + f(n-3)
	 * 
	 * 包含A,O,L的Prize String的个数的g(n)：
	 * 应为只包含A,O的合法字符串有f(n)个
	 * 包含一个L的合法字符串有f(n-1)f(0) + f(n-2)f(1) + ... + f(1)f(n-2) + f(0)f(n-1)个
	 * 所以：
	 * g(n) = f(n) + f(n-1)f(0) + f(n-2)f(1) + ... + f(1)f(n-2) + f(0)f(n-1)
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		long s = System.currentTimeMillis();
		System.out.println("count = " + g(30));
		System.out.println((System.currentTimeMillis() - s) + " ms");
	}

	public static long g(int n) {
		long[] f = new long[n+1];
		f[0] = 1;
		f[1] = 2;
		f[2] = 4;
		for (int i = 3; i < f.length; i ++) {
			f[i] = f[i-1] + f[i-2] + f[i-3];
		}
		long g = f[n];
		for (int i = 0; i <= n-1; i ++) {
			g += f[i]*f[n-1-i];
		}
		return g;
	}
}
